#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
//struct TreeNode {
//    int val;
//    struct TreeNode* left;
//    struct TreeNode* right;
//    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//};
//class Solution {
//public:
//    vector<vector<int> > Print(TreeNode* pRoot) {
//        // write code here
//        TreeNode* head = pRoot;
//        vector<vector<int> > v;
//        if (head == nullptr)
//            return v;
//        queue<TreeNode* >tmp;
//        tmp.push(head);
//        TreeNode* ptr;
//        while (!tmp.empty())
//        {
//            vector<int> row;
//            int sz = tmp.size();
//            for (int i = 0; i < sz; i++)
//            {
//                ptr = tmp.front();
//                tmp.pop();
//                row.push_back(ptr->val);
//                if (ptr->left)
//                    tmp.push(ptr->left);
//                if (ptr->right)
//                    tmp.push(ptr->right);
//            }
//            v.push_back(row);
//        }
//        return v;
//    }
//};

//int main()
//{
//    TreeNode* root = new TreeNode(1);
//    root->left = new TreeNode(2);
//    root->right = new TreeNode(3);
//    root->right->left = new TreeNode(4);
//    root->right->right = new TreeNode(5);
//    
//    Solution s;
//    auto ret = s.Print(root);
//    for (int i = 0; i < ret.size(); i++)
//    {
//        for (int j = 0; j < ret[i].size(); j++)
//            cout << ret[i][j] << " ";
//        cout << endl;
//    }
//    //delete root->right->right;
//    //delete root->right->left;
//    //delete root->right;
//    //delete root->left;
//    delete root;
//
//}


// struct TreeNode {
//	int val;
//	struct TreeNode *left;
//	struct TreeNode *right;
// };
//
//struct TreeNode* reConstructBinaryTree(int* preOrder, int preOrderLen, int* vinOrder, int vinOrderLen) {
//    struct TreeNode* pRoot = 0;
//    int tmp = 0;
//    if (preOrder == NULL || preOrderLen == 0)
//        return NULL;
//    pRoot = (struct TreeNode*)calloc(0, sizeof(struct TreeNode));
//    pRoot->val = preOrder[0];
//    while (preOrder[0] != vinOrder[tmp])
//        tmp++;
//    pRoot->left = reConstructBinaryTree(preOrder + 1, tmp, vinOrder, tmp);
//    pRoot->right = reConstructBinaryTree(preOrder + tmp + 1, preOrderLen - tmp - 1, vinOrder + tmp + 1, preOrderLen - tmp - 1);
//    return pRoot;
//}




 struct TreeNode {
   int val;
   struct TreeNode *left;
   struct TreeNode *right;
   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  };
 
class Solutional {
public:
    TreeNode* reConstructBinaryTree(vector<int> preOrder, vector<int> vinOrder) {
        // write code here
        int tmp = 0;
        if (preOrder.empty() || vinOrder.empty())
            return nullptr;
        TreeNode* pRoot = new TreeNode(preOrder[0]);
        while (preOrder[0] != vinOrder[tmp])
            tmp++;
        pRoot->left = reConstructBinaryTree(vector<int>(preOrder.begin() + 1, preOrder.begin() + tmp + 1), vector<int>(vinOrder.begin(), vinOrder.begin() + tmp));
        pRoot->right = reConstructBinaryTree(vector<int>(preOrder.begin() + tmp + 1, preOrder.end()), vector<int>(vinOrder.begin() + tmp + 1, vinOrder.end()));
        return pRoot;
    }
    void destroyTree(TreeNode* root) {
        if (root == nullptr) return;
        destroyTree(root->left);
        destroyTree(root->right);
        delete root;
    }
};


int main()
{
    vector<int> pre = { 1,2,4,7,3,5,6,8 };
    vector<int> vin = { 4,7,2,1,5,3,8,6 };
    Solutional s1;
    TreeNode* pRoot = s1.reConstructBinaryTree(pre, vin);

    s1.destroyTree(pRoot);
    return 0;
}